package microsoft;

/**
 * 1404.II.将二进制表示减到 0 的步骤数
 *
 * 二进制字符串，如果数字为偶数除2，奇数减1
 *
 * 例1：S="011100"，则十进制数28，返回值7（变为0需要7步）
 * 除2得到14
 * 除2得到7
 * 减1得到6
 * 除2得到3
 * 减1得到2
 * 除2得到1
 * 减1得到0
 */
public class binaryToZero {
    public static void main(String[] args) {
        System.out.println(new binaryToZero().numSteps2("0111001111000010"));
    }


    public int numSteps(String S) {
        int res = 0;

        boolean meet1 = false;

        for (int i=0; i<=S.length()-1; i++){
            if (S.charAt(i) == '0') {
                res += (meet1?1:0); //如果0为高位0，则意味者不用做任何操作，如果在1后的0，则这里只需要除2；
            } else {
                if (meet1) { //如果为1，且已经遇到过1了，非高位1，此需要先减1，后除2，两步
                    res += 2;
                } else {
                    meet1 = true; ////如果为1，且没有遇到过1（高位1），则只需要减1即可
                    res+=1;
                }
            }

        }

        return res;
    }

    /**
     * 转为十进制，字符串过长报错.
     */
    public int numSteps2(String S){
        int num = Integer.parseInt(S,2);
        int res = 0;

        while(num!=0){
            if (num%2==0){
                num = num/2;
            } else {
                num--;
            }
            res++;
        }

        return res;
    }


}
